﻿//力扣：560. 和为 K 的子数组
//https://leetcode.cn/problems/subarray-sum-equals-k/description/


//方法一：暴力法
//时间复杂度O(n^2)

//算法原理：
//我们逐个检查以每个元素为起点的所有子数组的和，如果该和等于 k，则计数器 ret 增加。这样可以遍历所有子数组组合，但效率较低。
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int ret = 0;                                    // 记录满足条件的子数组个数

        // 遍历每个可能的起始点
        for (int i = 0; i < n; i++) 
        {
            int temp = 0;                               // 累加前缀和，初始化为 0
            for (int j = i; j < n; j++) 
            {
                temp += nums[j];                        // 计算子数组 [i, j] 的和
                if (temp == k)                          // 如果和等于 k，计数器增加
                { 
                    ret++;
                }
            }
        }

        return ret;
    }
};




//方法二：前缀和+哈希表
//时间复杂度O(n)

// 算法原理：
//· 前缀和的定义：
//       假设我们用 sum[i] 表示从数组起点 0 到位置 i 的所有元素之和。
//       目标是找到「以 i 为结尾的和为 k 的子数组」。

//· 转换为前缀和问题：
//       为了得到「和为 k 的子数组」，我们想找到一个起始位置 x，使得 sum[i] - sum[x] = k。 
//       这可以重写为 sum[x] = sum[i] - k，也就是在位置 i 之前，我们要找有多少个位置 x 的前缀和 sum[x] 等于 sum[i] - k。

//· 哈希表的作用：为了快速找到等于 sum[i] - k 的前缀和个数，我们可以用一个哈希表 mp。

//       i. 在遍历数组时，随时更新当前的前缀和 sum。
//       ii. 每次遍历时，检查 sum - k 在哈希表 mp 中出现了多少次。
//       iii. 这些次数表示满足条件的子数组数，将这些次数加到计数器 ret 中。

//代码的关键思想是：通过哈希表 mp 来记录每一个前缀和出现的次数，并利用这一信息来判断是否存在符合条件的子数组。
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int ret = 0, sum = 0;                       // ret 用于记录符合条件的子数组数量
        unordered_map<int, int> mp;                 // 哈希表，用于存储前缀和出现的次数

        mp[0] = 1;// 初始化前缀和为 0 的次数为 1，避免漏掉前缀和为 0 的情况
        //简单来说，mp[0] = 1可以视作一种“哨兵”（sentinel），确保当子数组从起始位置就满足条件时不会被遗漏掉。

        for (int i = 0; i < n; i++) 
        {
            sum += nums[i];                         // 更新当前前缀和
            //if (mp.find(sum - k) != mp.end())
            if (mp.count(sum - k))                  // 判断是否存在前缀和使得 sum - (sum - k) = k
            {  
                ret += mp[sum - k];                 // 如果存在，则增加符合条件的子数组数量
            }
            mp[sum]++;                              // 更新哈希表中当前前缀和的出现次数
        }

        return ret;
    }
};
//ret += mp[sum - k];的解释：
//ret += mp[sum - k]; 的作用是检查在当前位置的前缀和为sum的情况下，是否存在某一个历史位置的前缀和为 sum - k。
//如果存在，则说明从该历史位置到当前位置的子数组和为k，我们将这些符合条件的子数组的数量累加到ret中。
//工作原理：
//    · sum表示当前的前缀和，而sum - k则是我们寻找的目标前缀和（使得从该目标位置到当前位置的元素和为k）。
//    · 如果mp[sum - k]存在，说明此前有若干位置的前缀和为sum - k，因此从这些位置到当前位置的子数组和均为k。
//    · mp[sum - k]存储了所有满足前缀和为sum - k的子数组数量，因此我们将它们加到ret中。


//前缀和加入哈希表时机的解释：
//在每次循环时，我们的前缀和sum都会增加当前元素nums[i]。但是，为了确保我们计算的是“从起始位置到当前位置的子数组和”，
//我们在检查是否存在满足条件的前缀和后，再更新哈希表中的sum出现次数。
//原因：
//如果我们在当前i位置就更新哈希表，则在后续的计算中可能会包含nums[i]这个元素自身，使得计算子数组和不再是“从某一位置到当前位置”的和，而是包含了i位置后的元素。
//先进行判断再更新哈希表中的sum出现次数，能够保证所有子数组和的正确性和完整性。